SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Circular convolution</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Circular convolution</span></span>

</h1>

</header>

<p><b>Circular convolution</b>, also known as <b>cyclic convolution</b>, is a special case of <b>periodic convolution</b>, which is the <a href="Convolution" title="Convolution">convolution</a> of two periodic functions that have the same period. Periodic convolution arises, for example, in the context of the <a href="Discrete-time_Fourier_transform" title="Discrete-time Fourier transform">discrete-time Fourier transform</a> (DTFT). In particular, the DTFT of the product of two discrete sequences is the periodic convolution of the DTFTs of the individual sequences. And each DTFT is a <a href="Periodic_summation" title="Periodic summation">periodic summation</a> of a continuous Fourier transform function (see <a href="Discrete-time_Fourier_transform#Relation_to_Fourier_Transform" title="Discrete-time Fourier transform">Discrete-time Fourier transform § Relation to Fourier Transform</a>). Although DTFTs are usually continuous functions of frequency, the concepts of periodic and circular convolution are also directly applicable to discrete sequences of data. In that context, circular convolution plays an important role in maximizing the efficiency of a certain kind of common filtering operation.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

<p>The <i>periodic convolution</i> of two T-periodic functions, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{_{T}}(t)}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{_{T}}(t)}</annotation>

</semantics>

</math></span><img src="./0dbf745360cd1499bb246e4c4a0537bbe08dd82e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.324ex; height:3.009ex;" alt="{\displaystyle h_{_{T}}(t)}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{_{T}}(t)}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{_{T}}(t)}</annotation>

</semantics>

</math></span><img src="./a14897f04bb0ca2d651dd456402e3c5795e26bc1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.314ex; height:3.009ex;" alt="{\displaystyle x_{_{T}}(t)}" loading="lazy"></span> can be defined as<b>:</b>

</p>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,}</annotation>

</semantics>

</math></span><img src="./2b0bfe76c540d8279bf99e84fbcbb3c5293f38b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:27.098ex; height:6.509ex;" alt="{\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,}" loading="lazy"></span>   <sup id="cite_ref-Jeruchim_1-0" class="reference"><a href="#cite_note-Jeruchim-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Udayashankara_2-0" class="reference"><a href="#cite_note-Udayashankara-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{o}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{o}}</annotation>

</semantics>

</math></span><img src="./3269d8ddf0283582f0152583b7a6970d58dbdc14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.869ex; height:2.343ex;" alt="{\displaystyle t_{o}}" loading="lazy"></span> is an arbitrary parameter.  An alternative definition, in terms of the notation of normal <i>linear</i> or <i>aperiodic</i> convolution, follows from expressing <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{_{T}}(t)}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{_{T}}(t)}</annotation>

</semantics>

</math></span><img src="./0dbf745360cd1499bb246e4c4a0537bbe08dd82e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.324ex; height:3.009ex;" alt="{\displaystyle h_{_{T}}(t)}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{_{T}}(t)}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{_{T}}(t)}</annotation>

</semantics>

</math></span><img src="./a14897f04bb0ca2d651dd456402e3c5795e26bc1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.314ex; height:3.009ex;" alt="{\displaystyle x_{_{T}}(t)}" loading="lazy"></span> as <a href="Periodic_summation" title="Periodic summation">periodic summations</a> of aperiodic components <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span>, i.e.<b>:</b>

</p>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{_{T}}(t)\ \triangleq \ \sum _{k=-\infty }^{\infty }h(t-kT)=\sum _{k=-\infty }^{\infty }h(t+kT).}</annotation>

</semantics>

</math></span><img src="./8e16a3e45ff1b3aa319ff41c534c02440489d379.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:43.955ex; height:7.009ex;" alt="{\displaystyle h_{_{T}}(t)\ \triangleq \ \sum _{k=-\infty }^{\infty }h(t-kT)=\sum _{k=-\infty }^{\infty }h(t+kT).}" loading="lazy"></span></dd></dl>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output table.numblk{border-collapse:collapse;border:none;margin-top:0;margin-right:0;margin-bottom:0}.mw-parser-output table.numblk>tbody>tr>td{vertical-align:middle;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2){width:99%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table{border-collapse:collapse;margin:0;border:none;width:100%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:first-child,.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:last-child{padding:0 0.4ex}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:nth-child(2){width:100%;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{padding:0}.mw-parser-output table.numblk>tbody>tr>td:last-child{font-weight:bold}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child{font-weight:unset}.mw-parser-output table.numblk>tbody>tr>td:last-child::before{content:"("}.mw-parser-output table.numblk>tbody>tr>td:last-child::after{content:")"}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::before,.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::after{content:none}.mw-parser-output table.numblk>tbody>tr>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:none;border-right:none;border-bottom:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:thin solid;border-right:thin solid;border-bottom:thin solid}.mw-parser-output table.numblk:target{color:var(--color-base,#202122);background-color:#cfe8fd}@media screen{html.skin-theme-clientpref-night .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}

/* end https://en.wikipedia.org/ */

</style><table role="presentation" class="numblk" style="margin-left: 0em;"><tbody><tr><td class="nowrap">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau =\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau \ \triangleq \ (h*x_{_{T}})(t)=(x*h_{_{T}})(t).}</annotation>

</semantics>

</math></span><img src="./f28230ac38315d388bf1b57c2b24f605d4f4917a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:81.894ex; height:6.509ex;" alt="{\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau =\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau \ \triangleq \ (h*x_{_{T}})(t)=(x*h_{_{T}})(t).}" loading="lazy"></span>    

</p>

</td> <td></td> <td class="nowrap"><span id="math_Eq.1" class="reference nourlexpansion" style="font-weight:bold;">Eq.1</span></td></tr></tbody></table>

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .cot-header-mainspace{background:#F0F2F5;color:inherit}.mw-parser-output .cot-header-other{background:#CCFFCC;color:inherit}@media screen{html.skin-theme-clientpref-night .mw-parser-output .cot-header-mainspace{background:#14181F;color:inherit}html.skin-theme-clientpref-night .mw-parser-output .cot-header-other{background:#003500;color:inherit}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cot-header-mainspace{background:#14181F;color:inherit}html.skin-theme-clientpref-os .mw-parser-output .cot-header-other{background:#003500;color:inherit}}

/* end https://en.wikipedia.org/ */

</style>

<th class="cot-header-mainspace" style="; font-size:87%; padding:0.2em 0.3em; text-align:center;"><div style="font-size:115%;margin:0 4em">Derivation of Eq.1</div>

</th></tr>

<tr>

<mtr>

<mtd>

</mrow>

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<mtext> is an arbitrary parameter</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<mtext> by periodicity</mtext>

</mrow>

</munder>

</mrow>

</mrow>

<mtext>substituting </mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munder>

</mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<mtext>substituting </mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \right]\quad t_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(u+kT)\cdot \underbrace {x_{_{T}}(t-u-kT)} _{x_{_{T}}(t-u),{\text{ by periodicity}}}\ du\right]\quad {\text{substituting }}u\triangleq \tau -kT\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(u+kT)\cdot x_{_{T}}(t-u)\right]\ du\\&=\int _{t_{o}}^{t_{o}+T}\underbrace {\left[\sum _{k=-\infty }^{\infty }h(u+kT)\right]} _{\triangleq \ h_{_{T}}(u)}\cdot x_{_{T}}(t-u)\ du\\&=\int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \quad {\text{substituting }}\tau \triangleq u\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./aa1a3acad1ad9e1ce3db7f2fb88c8d2ffd805dfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -22.338ex; width:101.399ex; height:45.843ex;" alt="{\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \right]\quad t_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(u+kT)\cdot \underbrace {x_{_{T}}(t-u-kT)} _{x_{_{T}}(t-u),{\text{ by periodicity}}}\ du\right]\quad {\text{substituting }}u\triangleq \tau -kT\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(u+kT)\cdot x_{_{T}}(t-u)\right]\ du\\&=\int _{t_{o}}^{t_{o}+T}\underbrace {\left[\sum _{k=-\infty }^{\infty }h(u+kT)\right]} _{\triangleq \ h_{_{T}}(u)}\cdot x_{_{T}}(t-u)\ du\\&=\int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \quad {\text{substituting }}\tau \triangleq u\end{aligned}}}" loading="lazy"></span></dd></dl>

</td></tr></tbody></table></div><p><br>

</p><p>Both forms can be called <i>periodic convolution</i>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup> The term <i>circular convolution</i><sup id="cite_ref-Udayashankara_2-1" class="reference"><a href="#cite_note-Udayashankara-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Priemer_4-0" class="reference"><a href="#cite_note-Priemer-4"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> arises from the important special case of constraining the non-zero portions of both <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> to the interval <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,T].}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0,T].}</annotation>

</semantics>

</math></span><img src="./d49a2b0474d5ee6d0e1967879a5489d3978f828c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.773ex; height:2.843ex;" alt="{\displaystyle [0,T].}" loading="lazy"></span> Then the periodic summation becomes a <i>periodic extension</i><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>b<span class="cite-bracket">]</span></a></sup>, which can also be expressed as a <i>circular function</i><b>:</b>

</p>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,}</annotation>

</semantics>

</math></span><img src="./22e6ba928c5de94b458820766f2d0dd431e4094a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.568ex; height:3.009ex;" alt="{\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,}" loading="lazy"></span> (<a href="Number#Real_numbers" title="Number">any real number</a>)<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>c<span class="cite-bracket">]</span></a></sup></dd></dl>

<p>And the limits of integration reduce to the length of function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span><b>:</b>

</p>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .}</annotation>

</semantics>

</math></span><img src="./9ab6a13631f65a54fa64742514088bcc6a6dfa70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:42.576ex; height:6.176ex;" alt="{\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .}" loading="lazy"></span><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>d<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>e<span class="cite-bracket">]</span></a></sup></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Discrete_sequences">Discrete sequences</h2></div>

<p>Similarly, for discrete sequences, and a parameter <b>N</b>, we can write a <b>circular convolution</b> of aperiodic functions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> as<b>:</b>

</p>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot \underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}}</annotation>

</semantics>

</math></span><img src="./4d49c81da094cd54509001dea3b0a1f5e2751d6a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.171ex; width:43.52ex; height:9.009ex;" alt="{\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot \underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}}" loading="lazy"></span></dd></dl>

<p>This function is <b>N</b>-periodic. It has at most <b>N</b> unique values. For the special case that the non-zero extent of both <i>x</i> and <i>h</i> are <i>≤ N</i>, it is reducible to <a href="Matrix_multiplication" title="Matrix multiplication">matrix multiplication</a> where the kernel of the integral transform is a <a href="Circulant_matrix" title="Circulant matrix">circulant matrix</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>A case of great practical interest is illustrated in the figure. The duration of the <b>x</b> sequence is <b>N</b> (or less), and the duration of the <b>h</b> sequence is significantly less. Then many of the values of the circular convolution are identical to values of <b>x∗h</b>,  which is actually the desired result when the <b>h</b> sequence is a <a href="Finite_impulse_response" title="Finite impulse response">finite impulse response</a> (FIR) filter. Furthermore, the circular convolution is very efficient to compute, using a <a href="Fast_Fourier_transform" title="Fast Fourier transform">fast Fourier transform</a> (FFT) algorithm and the <a href="Discrete_Fourier_transform#Circular_convolution_theorem_and_cross-correlation_theorem" title="Discrete Fourier transform">circular convolution theorem</a>.

</p><p>There are also methods for dealing with an <b>x</b> sequence that is longer than a practical value for <b>N</b>. The sequence is divided into segments (<i>blocks</i>) and processed piecewise. Then the filtered segments are carefully pieced back together. Edge effects are eliminated by <i>overlapping</i> either the input blocks or the output blocks. To help explain and compare the methods, we discuss them both in the context of an <b>h</b> sequence of length 201 and an FFT size of <i>N</i> = 1024.

</p>

<div class="mw-heading mw-heading3"><h3 id="Overlapping_input_blocks">Overlapping input blocks</h3></div>

<p>This method uses a block size equal to the FFT size (1024). We describe it first in terms of normal or <i>linear</i> convolution. When a normal convolution is performed on each block, there are start-up and decay transients at the block edges, due to the filter <i>latency</i> (200-samples). Only 824 of the convolution outputs are unaffected by edge effects. The others are discarded, or simply not computed. That would cause gaps in the output if the input blocks are contiguous. The gaps are avoided by overlapping the input blocks by 200 samples. In a sense, 200 elements from each input block are "saved" and carried over to the next block. This method is referred to as <b><a href="Overlap-save_method" class="mw-redirect" title="Overlap-save method">overlap-save</a></b>,<sup id="cite_ref-Rabiner_9-0" class="reference"><a href="#cite_note-Rabiner-9"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> although the method we describe next requires a similar "save" with the output samples.

</p><p>When an FFT is used to compute the 824 unaffected DFT samples, we don't have the option of not computing the affected samples, but the leading and trailing edge-effects are overlapped and added because of circular convolution. Consequently, the 1024-point inverse FFT (IFFT) output contains only 200 samples of edge effects (which are discarded) and the 824 unaffected samples (which are kept). To illustrate this, the fourth frame of the figure at right depicts a block that has been periodically (or "circularly") extended, and the fifth frame depicts the individual components of a linear convolution performed on the entire sequence. The edge effects are where the contributions from the extended blocks overlap the contributions from the original block. The last frame is the composite output, and the section colored green represents the unaffected portion.

</p>

<div class="mw-heading mw-heading3"><h3 id="Overlapping_output_blocks">Overlapping output blocks</h3></div>

<p>This method is known as <i><a href="Overlap-add_method" class="mw-redirect" title="Overlap-add method">overlap-add</a></i>.<sup id="cite_ref-Rabiner_9-1" class="reference"><a href="#cite_note-Rabiner-9"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> In our example, it uses contiguous input blocks of size 824 and pads each one with 200 zero-valued samples. Then it overlaps and adds the 1024-element output blocks. Nothing is discarded, but 200 values of each output block must be "saved" for the addition with the next block. Both methods advance only 824 samples per 1024-point IFFT, but overlap-save avoids the initial zero-padding and final addition.

</p>

<ul><li><a href="Convolution_theorem#Functions_of_discrete_variable_sequences" title="Convolution theorem">Convolution theorem</a></li>

<li><a href="Circulant_matrix" title="Circulant matrix">Circulant matrix</a></li>

<li><a href="Hilbert_transform#Discrete_Hilbert_transform" title="Hilbert transform">Discrete Hilbert transform</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Page_citations">Page citations</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width reflist-lower-alpha">

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><a href="#McGillem">McGillem and Cooper</a>, p 172 (4-6)</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><a href="#McGillem">McGillem and Cooper</a>, p 183 (4-51)</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><a href="#Oppenheim">Oppenheim and Shafer</a>, p 559 (8.59)</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><a href="#Oppenheim">Oppenheim and Shafer</a>, p 571 (8.114), shown in digital form</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><a href="#McGillem">McGillem and Cooper</a>, p 171 (4-22), shown in digital form</span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFJeruchimBalabanShanmugan2000" class="citation book cs1">Jeruchim, Michel C.; Balaban, Philip; Shanmugan, K. Sam (October 2000). <i>Simulation of Communication Systems: Modeling, Methodology and Techniques</i> (2nd ed.). New York: Kluwer Academic Publishers. pp. <span class="nowrap">73–</span>74. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-30-646267-2</bdi>.</cite></span>

</li>

<cite id="CITEREFUdayashankara2010" class="citation book cs1">Udayashankara, V. (June 2010). <i>Real Time Digital Signal Processing</i>. India: Prentice-Hall. p. 189. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-8-12-034049-7</bdi>.</cite></span>

</li>

<cite id="CITEREFPriemer1991" class="citation book cs1">Priemer, Roland (July 1991). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=QBT7nP7zTLgC&q=Priemer,+Roland"><i>Introductory Signal Processing</i></a>. Advanced Series in Electrical and Computer Engineering. Vol. 6. Teaneck, N.J.: World Scientific Pub Co Inc. pp. <span class="nowrap">286–</span>289. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9971-50-919-9</bdi>.</cite></span>

</li>

<cite id="CITEREFRabiner,_Lawrence_R.Gold,_Bernard1975" class="citation book cs1">Rabiner, Lawrence R.; Gold, Bernard (1975). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/theoryapplicatio00rabi/page/63"><i>Theory and application of digital signal processing</i></a></span>. Englewood Cliffs, N.J.: Prentice-Hall. pp. <span class="nowrap">63–</span>67. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-914101-4</bdi>.</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ol><li value="5"><cite id="Oppenheim" class="citation book cs1"><a href="Alan_V._Oppenheim" title="Alan V. Oppenheim">Oppenheim, Alan V.</a>; <a href="Ronald_W._Schafer" title="Ronald W. Schafer">Schafer, Ronald W.</a>; Buck, John R. (1999). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/discretetimesign00alan"><i>Discrete-time signal processing</i></a></span> (2nd ed.). Upper Saddle River, N.J.: Prentice Hall. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/discretetimesign00alan/page/548">548</a>, 571. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-754920-2</bdi>.</cite></li>

<li><cite id="McGillem" class="citation book cs1">McGillem, Clare D.; Cooper, George R. (1984). <i>Continuous and Discrete Signal and System Analysis</i> (2 ed.). Holt, Rinehart and Winston. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-03-061703-0</bdi>.</cite></li></ol>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFOppenheim,_Alan_V.Willsky,_with_S._Hamid1998" class="citation book cs1">Oppenheim, Alan V.; Willsky, with S. Hamid (1998). <i>Signals and Systems</i>. Pearson Education. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-814757-4</bdi>.</cite></li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-17" href="https://en.wikipedia.org/wiki/?title=Circular_convolution&oldid=1263574327">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>